#include <stdio.h>

#include "bitree.h"

// 交换指针
void swap(BiTree* a, BiTree* b) {
    BiTree temp = *a;
    *a = *b;
    *b = temp;
}

// 交换左右子树
void Exchange(BiTree t) { swap(&t->lchild, &t->rchild); }

// 先序遍历交换左右子树
void PreOrderExchange(BiTree t) {
    if (!t) return;
    Exchange(t);
    PreOrderExchange(t->lchild);
    PreOrderExchange(t->rchild);
}

// 后序遍历交换左右子树
void PostOrderExchange(BiTree t) {
    if (!t) return;
    PostOrderExchange(t->lchild);
    PostOrderExchange(t->rchild);
    Exchange(t);
}

// 层序遍历交换左右子树
void LevelOrderExchange(BiTree t) {
    if (!t) {
        return;  // 空树直接返回
    }
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);
        Exchange(p);  // 交换当前结点的左右子树
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
    }
}

void TestExchange(ElemType arr[], int n) {
    printf("test begin\n");

    BiTree root;
    LevelOrderCreateBiTree(&root, arr, n);

    printf("先序遍历：\n");
    PreOrderVisit(root);
    printf("\n");

    PreOrderExchange(root);
    PostOrderExchange(root);
    LevelOrderExchange(root);

    printf("交换后先序遍历：\n");
    PreOrderVisit(root);
    printf("\n");

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    TestExchange(arr1, 1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    TestExchange(arr2, 7);

    ElemType arr3[] = {'A', 'B', 'C', '#', '#', 'D', 'E', '#',
                       'F', '#', '#', 'G', '#', '#', '#'};
    TestExchange(arr3, 15);

    return 0;
}